//https://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134?tpId=13&tqId=2276652&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//矩阵的动态规划
//矩阵的最长路径和

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

class Solution {
  public:
    int maxValue( vector<vector<int> >& grid) {
        
        int m = grid.size(); //行
        int n = grid[0].size();//列
        std::cout << m << std::endl;
        std::cout << n << std::endl;

        std::vector<std::vector<int>> dp_res(m,vector<int>(n,0));
        dp_res[0][0] = grid[0][0];
        //第一列
        for (int i = 1; i < m; i++)
            dp_res[i][0] += grid[i][0] + dp_res[i-1][0];
        //第一行
        for (int j = 1; j < n; j++)
            dp_res[0][j] += grid[0][j] + dp_res[0][j-1];
        //遍历后续每一个位置
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp_res[i][j] += max(dp_res[i - 1][j], dp_res[i][j - 1]) + grid[i][j];
            }
        }
        // 
        return dp_res[m - 1][n - 1];
    }
};